import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;

public abstract class HeapSort
{
    public int A[];
    public int last;
    public String filename;   
    public long keyComparisons;
    
    public HeapSort(int N, String filename)
    {
        this.A = new int[N];
        this.filename = filename;
        this.last = -1;
        this.keyComparisons = 0;
    }
    
    public void heapify(int [] L)
    {
        if(L.length == 0)
        {
            return;
        }
        for(int i = 0; i <L.length;i++)
        {
            A[i+last+1] = L[i];
        }
        last = last + L.length;
        for(int i = last/2 ; i>=0; i--)
        {
            percolateDown(i);
        }
    }
    
    public void extractMinEstandar()
    {
        if(last == -1)
        {
            return;
        }
        int elem = A[0];
        A[0] = A[last];
        A[last] = elem;
        last = last-1;
        percolateDown(0);
    }
    
    public void percolateDown(int pos)
    {
	int aux = A[pos];
	int leftChild, rightChild, smaller;
	for (;;)
	{
            leftChild  = 2 * pos + 1 ;	
            rightChild = leftChild+1;
            if (leftChild > last)
	    {
                break;
            }
            if( leftChild == last || A[leftChild] > A[rightChild])
            {
                smaller = leftChild;
            }
            else
            {
                smaller = rightChild;
            }
            if (A[smaller] > aux)
            {
                A[pos] = A[smaller];
                pos = smaller;
            }
            else
            {
                break;	
            }
            keyComparisons += 2;
        }
	A[pos] = aux;
    }
    
    public void insert(int value)
    {
        last = last + 1;
        int aux  = last;
        int parent = (aux-1)/2;
        int i = 0;
        while(value>A[parent] && aux!=parent)
        {
            A[aux] = A[parent];
            aux = parent;
            parent = (aux-1)/2;
            keyComparisons++;
        }
        keyComparisons++;
        A[aux] = value;
    }
    
    public void printer()
    {
        try 
        {
            PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(filename)));
            for(int i = 0; i<A.length; i++)
            {
                out.print(A[i]+"\n");
            }
            out.close();
        } 
        catch (IOException ex)
        {
            System.out.println("Can't create a file");
        }
    }
    
    public void extractMaxWegener()
    {   
        if(last == -1) 
        {
            return;
        }
        
        int aux = A[0];
        int hole = 0;
        int bigger;
        int leftChild, rightChild;
        
        // parte 1: bajamos el hole
        while(true) {
            leftChild = 2*hole + 1;
            rightChild = leftChild+1;
            if(leftChild > last) break;
            if(leftChild == last || A[leftChild] > A[rightChild]) {
                bigger = leftChild;
            }
            else {
                bigger = rightChild;
            }
            /*
             * if (left = last) bigger <- left
             * else
             *   comp<- comp + 1
             *   if A[left] > A[right] bigger <- left
             *   else bigger <- right
             */
            A[hole] = A[bigger];
            hole = bigger;
            keyComparisons += 1;
        }
        // parte 2: recuperar la condicion de heap. rellenar el hole.
        while(true) {
            int parent = (hole-1)/2;
            if(A[last] > A[parent]) {
                A[hole] = A[parent];
                hole = parent;
            }
            else {
                A[hole] = A[last];
                A[last] = aux;
                last -= 1;
                break;
            }
            keyComparisons++;
        }
    }

    abstract void buildHeap(int[] L);
    abstract void extractMax();

    public long getKeyComparisons() {
        return keyComparisons;
    }
}
